/*
 * Ordenamiento.c
 *
 *  Created on: 27/03/2012
 *      Author: putaro
 */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <ctype.h>

/*
 * Pre: El parámetro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Selection Sort.
 */
void selectionSort(unsigned char* const vector ,
					const unsigned long int tamanio) {
	unsigned long int i , minimo;
	for (i = 0 ; i < tamanio - 1 ; i++) {
	    unsigned long int j;
	    unsigned char aux;
		minimo = i;
	    for (j = i + 1 ; j < tamanio ; j++) {
	        if (toupper(vector[j]) < toupper(vector[minimo])) {
	            minimo = j;
	        }
	    }
	    aux = vector[i];
	    vector[i] = vector[minimo];
	    vector[minimo] = aux;
	}
}

/*
 * Pre: Los parámetros son no nulos.
 * Post: Se ha aplicado el algoritmo Merge a las entradas.
 */
void merge(unsigned char* const vector1, const unsigned long int tamanio1,
			unsigned char* const vector2, const unsigned long int tamanio2,
			unsigned char* const vector3) {
    long int x1 , x2 , x3;
    x1 = 0;
    x2 = 0;
    x3 = 0;
    while ((x1 < tamanio1) && (x2 < tamanio2)) {
        if (toupper(vector1[x1]) < toupper(vector2[x2])) {
            vector3[x3] = vector1[x1];
            x1++;
        } else {
            vector3[x3] = vector2[x2];
            x2++;
        }
        x3++;
    }
    while (x1 < tamanio1) {
        vector3[x3] = vector1[x1];
        x1++;
        x3++;
    }
    while (x2 < tamanio2) {
        vector3[x3] = vector2[x2];
        x2++;
        x3++;
    }
}

/*
 * Pre: El parámetro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Merge Sort.
 */
void mergeSort(unsigned char* const vector , const unsigned long int tamanio) {
	unsigned char *vector1 , *vector2;
	unsigned long int tamanio1 , tamanio2;
    int x , y;
    if (tamanio > 1) {
        if ((tamanio % 2) == 0)
            tamanio1 = tamanio2 = (unsigned long int) (tamanio / 2);
        else {
            tamanio1 = (unsigned long int) (tamanio / 2);
            tamanio2 = tamanio1 + 1;
        }
        vector1 = malloc(sizeof(unsigned char) * tamanio1);
        vector2 = malloc(sizeof(unsigned char) * tamanio2);
        for (x = 0 ; x < tamanio1 ; x++)
            vector1[x] = vector[x];
        for (y = 0 ; y < tamanio2 ; x++ , y++)
            vector2[y] = vector[x];
        mergeSort(vector1 , tamanio1);
        mergeSort(vector2 , tamanio2);
        merge(vector1 , tamanio1 , vector2 , tamanio2 , vector);
        free(vector1);
        free(vector2);
    }
}

/*
 * Pre: Los parámetros son no nulos.
 * Post: Se ha aplicado el algoritmo Merge a las entradas.
 */
void mergeInverso(unsigned char* const vector1, const unsigned long int tamanio1,
			unsigned char* const vector2, const unsigned long int tamanio2,
			unsigned char* const vector3) {
    long int x1 , x2 , x3;
    x1 = 0;
    x2 = 0;
    x3 = 0;
    while ((x1 < tamanio1) && (x2 < tamanio2)) {
        if (toupper(vector1[x1]) > toupper(vector2[x2])) {
            vector3[x3] = vector1[x1];
            x1++;
        } else {
            vector3[x3] = vector2[x2];
            x2++;
        }
        x3++;
    }
    while (x1 < tamanio1) {
        vector3[x3] = vector1[x1];
        x1++;
        x3++;
    }
    while (x2 < tamanio2) {
        vector3[x3] = vector2[x2];
        x2++;
        x3++;
    }
}

/*
 * Pre: El parámetro vector es no nulo.
 * Post: Se ha ordenado el vector por el algoritmo Merge Sort.
 */
void mergeSortInverso(unsigned char* const vector , const unsigned long int tamanio) {
	unsigned char *vector1 , *vector2;
	unsigned long int tamanio1 , tamanio2;
	int x , y;
	if (tamanio > 1) {
		if ((tamanio % 2) == 0)
			tamanio1 = tamanio2 = (unsigned long int) (tamanio / 2);
	    else {
	        tamanio1 = (unsigned long int) (tamanio / 2);
	        tamanio2 = tamanio1 + 1;
	    }
	    vector1 = malloc(sizeof(unsigned char) * tamanio1);
	    vector2 = malloc(sizeof(unsigned char) * tamanio2);
	    for (x = 0 ; x < tamanio1 ; x++)
	        vector1[x] = vector[x];
	    for (y = 0 ; y < tamanio2 ; x++ , y++)
	        vector2[y] = vector[x];
	    mergeSortInverso(vector1 , tamanio1);
	    mergeSortInverso(vector2 , tamanio2);
	    mergeInverso(vector1 , tamanio1 , vector2 , tamanio2 , vector);
	    free(vector1);
	    free(vector2);
	}
}

